package 算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class 只有两个功能的键盘 {
    public static void main(String[] args) {
        int i = new 只有两个功能的键盘().missingNumber(new int[]{3,0,1});
        System.out.println(i);
    }
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for(int i= 0; i < nums.length; i++){
            res ^= nums[i];
        }
        return res;
    }
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for(int i= 0; i < nums.length; i++){
            res ^= i^nums[i];
        }
        return res;
    }
    public int minSteps(int n) {
        if(n < 6) return n;
        int[] dt = new int[n+1];
        dt[1] = 1;
        for(int i = 2; i <= n; i++){
            List<Integer> su = suShu(i);
            if(su.size() == 0){
                //代表是一个素数
                dt[i] = i;
            }else {
                int minS = dt[su.get(0)] + i / su.get(0) ;
                for(int j = 1; j < su.size(); j++) {
                    minS = Math.min(minS, dt[su.get(j)] + i / su.get(j));
                }
                dt[i] = minS;
            }
        }
        return dt[n];
    }
    //返回n的素数，不包含0与它本身
    public List<Integer> suShu(int n){
        List<Integer> res = new ArrayList();
        for(int i = 2; i < n/2; i++){
            if(n % i == 0){
                res.add(i);
                res.add(n/i);
            }
        }
        return res;
    }
}
